package com.lw.leetcode.stack.c;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA.
 * stack
 * 239. 滑动窗口最大值
 * 剑指 Offer 59 - I. 滑动窗口的最大值
 *
 * @author liw
 * @version 1.0
 * @date 2021/9/26 17:49
 */
public class MaxSlidingWindow {

    public static void main(String[] args) {
        MaxSlidingWindow test = new MaxSlidingWindow();

        // [3,3,5,5,6,7]
        int[] arr = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;

        // [1, -1]
//        int[] arr = {1, -1};
//        int k = 1;
        int[] ints = test.maxSlidingWindow(arr, k);
        System.out.println(Arrays.toString(ints));
    }


    public int[] maxSlidingWindow(int[] nums, int k) {
        int length = nums.length;
        if(length == 0) {
            return new int[0];
        }
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            int num = nums[i];
            while (!list.isEmpty() && list.getLast() < num) {
                list.pollLast();
            }
            list.add(num);
        }
        int len = nums.length - k + 1;
        int[] arr = new int[len];
        arr[0] = list.peek();
        int index = 1;
        for (int i = k; i < length; i++) {
            int num = nums[i];
            while (!list.isEmpty() && list.getLast() < num) {
                list.pollLast();
            }
            list.add(num);
            if (nums[i - k] == list.peek()) {
                list.poll();
            }
            arr[index++] = list.peek();
        }
        return arr;
    }

}
